package com.sunny;

public class Main {

    public int solve(String a, String b){

        if(null == a || null == b){
            return 0;
        }

        if("".equals(a))
            return b.length();
        if("".equals(b))
            return a.length();

        if(a.length() > b.length()){
            String tmp = a;
            a = b;
            b = tmp;
        }

        int[][] dp = new int[a.length()+1][b.length()+1];

        dp[0][0] = 0;

        int startj = 1;
        for(int i=1;i<a.length();i++){

            for(int j=startj;j<b.length();j++){

                if(a.charAt(i-1) == b.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                    startj = j+1;
                }else{
                    dp[i][j] = Integer.min(dp[i][j-1],dp[i-1][j])+1;
                }

            }
        }

        return dp[a.length()][b.length()];
    }

}
